1. Field of the Invention
The present invention is related to the field of data communications networks, and, more particularly, to the classification of packets and flows within a data communications network.
2. Description of the Related Art
Communication over the Internet and other data communication networks typically involves the transmission of “packetized” message segments. Packetized message segments are discrete packets of information that are separately transmitted from a source host to a destination host through various intermediate nodes, or network routers. Depending on various factors, such as network congestion, different packets carrying portions of the same underlying message may be routed to the destination over different paths. It is the task of the routers to direct each packet so that it efficiently reaches its proper destination. Increasingly, routers are used to effect various actions that are to be taken in handling packets transmitted over a data communication network. This typically requires that the packets be classified according to predefined criteria.
A router can classify incoming packets based upon information contained in each packet's header and information provided in the router's own table of classification rules referred to as a router table. The router table provides a set of rules whose form can be generalized by the 2-tuple, (F,A), where F represents a filter and A represents a corresponding action. The action element specifies the particular action to be performed when the packet information matches the corresponding filter. For example, a filter can be composed of fields that represent the packet's source address, its destination address, a particular protocol, and a port number. If the fields match the corresponding ones of the packet's header, then the rule specifies the action to be taken. The action can, for example, dictate that a packet be dropped, that the packet be forwarded along a specific output link, or that a specified amount of bandwidth be reserved. Thus, packet classification, broadly described, is the process of finding a match and, based on the match, determining which rule-dictated action is to be taken regarding the particular packet.
It can occur that a router table contains more than one filter component that matches the information contained in a packet's header. Accordingly, it is typically necessary for the sake of efficient routing of data packets to have some way of resolving a conflict due to a multiplicity of matches. One technique is to assign each rule a priority and select from among several conflicting matches the rule that has the highest priority.
With respect to routing a data packet based upon a destination address in the packet's header, the filters of the router table typically comprise binary strings referred to as prefixes that are compared to a binary string representing the destination address. In this context, conflict resolution operates by assigning a highest priority to the filter that has the most bits, or “longest prefix,” matching the binary string of the destination address.
Various data structures based on router table rules have been constructed to facilitate the classification of data packets as described. Conventional data structures, though, often suffer from drawbacks. These drawbacks include excessive cache misses during insert and delete operations that may be needed to update the data structure based on changes in the underlying router table. Other drawbacks include excessive memory usage, as when, for example, the data structure uses multiple memory locations to store an identical element. Accordingly, there is yet lacking an effective and efficient data structure for classifying data packets transmitted over a data communications network.